// 实现int sqrt(int x)函数，计算并返回x的平方根（只保留整数部分），其中x是非负整数

// 思路： 二分查找，每次判断midVal的平方是否小于等于target，并记录一次结果，更新left 和right缩小区间
// 时间复杂度为Ologn
// 空间复杂度为O1

function mySqrt(x) {
    let left = 0
    let right = x
    let ans = -1
    while (left <= right) {
        let mid = Math.floor((right - left) / 2) + left
        let squareVal = mid * mid
        if (squareVal <= x) {
            ans = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return ans
}

console.log(mySqrt(4))